from search import *



#Defino el problema a tratar
# se le pasa por parametro un bool 'dot'. Si es True imprime en stdout los nodos para el graphviz
class OchoPuzzle(Problem):
	
    def __init__(self,dot=False):
        self.initial = '281463075'
        self.goal    = '123804765'
        self.nodos_expandidos = 0
        self.dot = dot
        if dot:
          print "digraph{"
          print "concentrate=true"
          print "node [shape = box ]"
          print self.initial+" [color=blue, style=filled]"
          print self.goal   +" [color=red,  style=filled]"
        
    def __del__(self):
        if self.dot:
          print "}"


    def successor(self, state):
        "Array de sucesores posibles (action,estado)"
        "El factor de ramificacion va a ser 4 (max cant de sucesores)"
        index_zero = state.index('0')
        ret = []
      
        if index_zero > 2:    ret.append( (0, self.mover(state,index_zero,-3) ))
        if index_zero < 6:    ret.append( (1, self.mover(state,index_zero,+3) ))
        if index_zero%3 != 0: ret.append( (2, self.mover(state,index_zero,-1) ))
        if index_zero%3 != 2: ret.append( (3, self.mover(state,index_zero,+1) ))

        self.nodos_expandidos+=1 #cada vez q se piden sucesores, es q se esta expandiendo un nodo

        if self.dot:
          self.print_dot(state,ret)

        return ret
          
    def mover(self,st,i,x):
      s = [j for j in st]
      s[i], s[i+x] = s[i+x], s[i]
      s = reduce(operator.concat,s)
      return s
    
    def h1(self,node):
    	return 1

    def h2(self,node):
      cont = 0
      for i in range(9):
        if node.state[i] != '0' and node.state[i] != self.goal[i]:
          cont +=1
      return cont

    def h3(self,node):
      #sumatoria de la distancia de manhattan
      mann = 0
      for i in range(9):
        if node.state[i] != '0':
          correcto = self.goal.index(node.state[i])
          mann += (abs( correcto%3 - i%3) + abs(correcto/3 - i/3) ) 
      return mann

    def h4(self,node):
      #nilsson = manhattan + 2 por cada pieza q no tiene al sucesor al lado o
      #                    + 1 si esta en el medio

      nils = self.h3(node)
      for i in range(9):
        if node.state[i] != '0':
          if i == 4:
            nils +=1
          else:
            sucesor = False 
            actual = ord(node.state[i])
            if i > 2:
              if node.state[i-3] == chr(actual+1) or node.state[i-3] == chr(actual-1): sucesor = True 
            if i < 6:
              if node.state[i+3] == chr(actual+1) or node.state[i+3] == chr(actual-1): sucesor = True 
            if i%3 != 0:
              if node.state[i-1] == chr(actual+1) or node.state[i-1] == chr(actual-1): sucesor = True 
            if i%3 != 2:
              if node.state[i+1] == chr(actual+1) or node.state[i+1] == chr(actual-1): sucesor = True 

            if sucesor==False : nils+=2

      return nils


    def print_dot(self,actual,succ):
      for (i,j) in succ:
         print actual+ " -> "+j+";"
         print j+' [label="'+ j[0:3]+"\\n" +j[3:6]+"\\n" + j[6:9] +'"]'

"""Correr de a UNO por vez.
   Si se pasa True, hay q hacer python ej1.py > archivo.gv
   y despues dot -Tpdf archivo.gv > archivo.pdf"""

bfs = OchoPuzzle(True)
breadth_first_graph_search(bfs)
#print "Nodos Expandidos BFS:",bfs.nodos_expandidos

#dfs = OchoPuzzle()
#depth_first_graph_search(dfs)
#print "Nodos Expandidos DFS:",dfs.nodos_expandidos

#best = OchoPuzzle()
#best_first_graph_search(best,best.h1)
#print "Nodos Expandidos Best First H1:",best.nodos_expandidos

#best2 = OchoPuzzle(True)
#best_first_graph_search(best2,best2.h2)
#print "Nodos Expandidos Best First H2:",best2.nodos_expandidos

#best3 = OchoPuzzle()
#best_first_graph_search(best3,best3.h3)
#print "Nodos Expandidos Best First H3:",best3.nodos_expandidos

#best4 = OchoPuzzle()
#best_first_graph_search(best4,best4.h4)
#print "Nodos Expandidos Best First H4:",best4.nodos_expandidos

#astar1 = OchoPuzzle()
#astar_search(astar1,astar1.h1)
#print "Nodos Expandidos A* H1:",astar1.nodos_expandidos

#astar2 = OchoPuzzle()
#astar_search(astar2,astar2.h2)
#print "Nodos Expandidos A* H2:",astar2.nodos_expandidos

#astar3 = OchoPuzzle()
#astar_search(astar3,astar3.h3)
#print "Nodos Expandidos A* H3:",astar3.nodos_expandidos

#astar4 = OchoPuzzle()
#astar_search(astar4,astar4.h4)
#print "Nodos Expandidos A* H4:",astar4.nodos_expandidos
